package com.chengqs.algorithm.recursionsingle;

public class E03BinarySearch {
    public static int search(int[] arr, int target) {
        return f(arr, target, 0, arr.length - 1);
    }

    /**
     * <h3>递归(子问题)函数：查找 [i .. j] 范围内的目标</h3>
     *
     * @param arr    数组
     * @param target 待查找值
     * @param left   起始索引
     * @param right  结束索引
     * @return <p>找到返回索引</p><p>找不到返回 -1</p>
     */
    private static int f(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) >>> 1;
        if (target < arr[mid]) {
            return f(arr, target, left, mid - 1);
        } else if (arr[mid] < target) {
            return f(arr, target, mid + 1, right);
        } else {
            return mid;
        }
    }
}
